package com.leetcode.题库;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-02-26 16:56
 */
public class 题库_0015_三数之和 {

  static
  class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      Arrays.sort(nums);
      List<List<Integer>> answer = new ArrayList<>();

      for (int first = 0; first < nums.length; ++first) {
        if (first > 0 && nums[first] == nums[first - 1]) {
          continue;
        }
        int target = -1 * nums[first];
        int third = nums.length - 1;
        for (int second = first + 1; second < third; ++second) {
          if (second > first + 1 && nums[second] == nums[second - 1]) {
            continue;
          }
          while (second < third && nums[second] + nums[third] > target) {
            --third;
          }
          if (second < third && nums[second] + nums[third] == target) {
            answer.add(Arrays.asList(nums[first], nums[second], nums[third]));
          }
        }
      }
      return answer;
    }
  }

}
